{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 用Python实现堆排序算法【困难】"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "堆排序算法\n",
    "1，堆排序先自下而上构造最大堆（从小到大排序）\n",
    "2，然后交换堆顶和堆底，下沉最大值，堆的大小减小1\n",
    "3，将其余部分重新构造成一个最大堆\n",
    "4，不断重复2和3步骤，直到将数组变得从小到大排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](../data/堆排序.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================答题区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================答题区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================提示区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 提示：最大堆满足 arr[i] >= arr[2*i+1] and arr[i]>=arr[2*i+2]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================提示区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 5, 5, 6, 6, 6]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#==============================答案区==============================#\n",
    "# 解题思路：最大堆满足 arr[i] >= arr[2*i+1] and arr[i]>=arr[2*i+2]\n",
    "\n",
    "\n",
    "# 对不满足最大堆条件的节点进行交换，i为节点序号，n为堆的大小\n",
    "def swap_node(arr,i,n):\n",
    "    if 2*i+2<=n-1 and arr[2*i+2] > max(arr[2*i+1],arr[i]):\n",
    "        arr[i],arr[2*i+2] = arr[2*i+2],arr[i]\n",
    "        swap_node(arr,2*i+2,n)\n",
    "    elif 2*i+1<=n-1 and arr[2*i+1] > arr[i]:\n",
    "        arr[i],arr[2*i+1] = arr[2*i+1],arr[i]\n",
    "        swap_node(arr,2*i+1,n)\n",
    "    else:\n",
    "        pass\n",
    "    \n",
    "def heap_sort(arr):\n",
    "    # 初始化堆\n",
    "    for i in range(len(arr)//2-1,-1,-1):\n",
    "        swap_node(arr,i,len(arr))\n",
    "    # 排序过程\n",
    "    for n in range(len(arr),1,-1):\n",
    "        # 交换顶底\n",
    "        arr[0],arr[n-1] = arr[n-1],arr[0]\n",
    "        # 从顶开始重建新的堆\n",
    "        swap_node(arr,0,n-1)\n",
    "    return(arr)\n",
    "\n",
    "heap_sort([1,1,1,3,3,3,2,2,2,6,6,6,5,5,5])\n",
    "\n",
    "#==============================答案区==============================#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](../Python与算法之美.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
